package algorithm.heap;

import java.util.Random;

/**
 * @author bingo
 * @Description     最小索引堆 未优化
 * @Date 2018/4/22
 */
public class MinIndexHeap<Item extends Comparable>  {

    public Item[] data;

    public Integer count;

    public Integer size;

    private Integer[] indexs;

    public MinIndexHeap(Integer size) {
        this.data = (Item[])new Comparable[size+1];
        this.count = 0;
        this.size = size;
        this.indexs = new Integer[size+1];
    }
    public MinIndexHeap() { }
    /**传入index是针对用户而言的，索引从0开始*/
    public  void insert(Integer index,Item item){
        index = index+1;
        data[index] = item;
        indexs[count+1]=index;
        count++;
        shiftUp(count);
        }
    private void shiftUp(int k) {
        while (k > 1 && data[indexs[k]].compareTo(data[indexs[k/2]])<0){
            int    temp = indexs[k/2];
            indexs[k/2] = indexs[k];
            indexs[k] = temp;
            k=k/2;
        }

    }
    public  int extractMinIndex(){

        int temp = indexs[1]-1;
        indexs[1] = indexs[count];
        indexs[count] = temp;
        count--;
        shiftDown(1);

        return  temp;
    }
    public  Item getItem(int index){

        return data[index+1];
    }
    private void shiftDown(int k) {
        while (2*k <= count){
            int j=2*k;
            if(j+1<=count&&data[indexs[j+1]].compareTo(data[indexs[j]])<0){
                j++;
            }

            if(data[indexs[k]].compareTo(data[indexs[j]])<=0){
                break;
            }
            int temp = indexs[k];
            indexs[k] = indexs[j];
            indexs[j] = temp;
            k=j;
        }
    }
    public  Integer size(){
        return size;
    }
    public boolean isEmpty(){
        return count==0;
    }

    public void  change(int index,Item item){
        index = index + 1;
        data[index] = item;
        for(int i=1;i<indexs.length;i++){
            if(index==indexs[i]){
               shiftUp(indexs[i]);
               shiftDown(indexs[i]);
               return;
            }
        }
    }
    public static void main(String[] args) {
        MinIndexHeap minHeap = new MinIndexHeap(51);
        Random random = new Random();
        for(int i=0;i<50;i++){
            minHeap.insert(i,new Integer(i));
        }

         minHeap.change(10,25);
        for(int i=0;i<50;i++){
            Integer  index =  (Integer)minHeap.extractMinIndex();
            System.out.println("index:"+index+"---\t"+minHeap.getItem(index)+",\t");
        }
    }



}



